package com.Offer;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/*
    面试题60：n个骰子的点数
    把n个骰子扔到地上，所有的骰子朝上一面的点数和为s，输入n，打印出s的所有可能的值出现的概率
 */
public class demo60 {

    public static void main(String[] args) {
        //解法一的主函数：
/*        n = 2;
        pProbabilities = new int[maxValue*n-n+1];
        for (int i = 1;i <= maxValue;i++){
            Probability(n,i);
        }
        for (int i = 0; i < pProbabilities.length; i++) {
            System.out.print(pProbabilities[i]+" ");
        }
        System.out.println();
        PrintProbability();*/

        //解法二的主函数：
        Map<Integer, Double> integerDoubleMap = printProbability(2);
        Iterator<Map.Entry<Integer,Double>> iterator = integerDoubleMap.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer,Double> entry = iterator.next();
            System.out.println(entry.getValue());
        }
    }


    //解法一：递归 思路

    private static int maxValue = 6;
    private static int[] pProbabilities;
    private static int n;

    public static void PrintProbability(){
        if (pProbabilities == null)
            return;
        int total = (int) Math.pow(6,n);
        for (int i = 0; i < pProbabilities.length; i++) {
            double a = (double)pProbabilities[i] / total;
            System.out.print(a+" ");
        }
    }

    public static void Probability(int current,int sum){
        if(current == 1){
            pProbabilities[sum - n]++;
            return;
        }

        for(int i = 1;i <= maxValue;i++){
            //sum+i表示骰子的和，比如我们现在要计算2个骰子中3出现的次数分别是1+2和2+1的情况
            // 所以sum+i可以是1+2或者2+1，得到的s用于存放在相对应的数组下标的位置
            //比如说2骰子s的所有情况是2~12，和为3的数组下标位为1，sum-n的值就是得到1这个下标
            Probability(current-1,sum+i);
        }
    }
    /*-----------------------------------------------------*/

    //基于循环
    public static Map<Integer,Double> printProbability(int number){
        Map<Integer,Double> probabilityMap = new HashMap<>();
        if (number < 1)
            return probabilityMap;
        int g_maxValue = 6;
        int[][] probabilities = new int[2][g_maxValue*number+1];
        int flag = 0;

        // 当第一次抛掷骰子时，有 6 种可能，每种可能出现一次
        // 第一个骰子投完的结果存到了 probabilities[0]
        for(int i = 1;i <= g_maxValue;i++){
            probabilities[0][i] = 1;
        }

        //从第二次开始掷骰子，假设第一个数组中的第 n 个数字表示骰子和为 n 出现的次数
        for(int k = 2;k <= number;k++){

            //第k次掷骰子，和最小为 k，小于k的情况是不可能发生的,令不可能发生的次数设置为0！
            for(int i = 0;i < k;i++){
                probabilities[1-flag][i] = 0;
            }

            // 第 k 次掷骰子，和最小为 k，最大为 g_maxValue*k
            for(int i = k;i <= g_maxValue*k;i++){
                // 初始化，因为这个数组要重复使用，上一次的值要清 0
                probabilities[1-flag][i] = 0;
                for(int j = 1;j <= i && j <= g_maxValue;j++){
                    probabilities[1-flag][i] += probabilities[flag][i-j];
                }
            }
            // 若 flag=0，1-flag 用的就是数组 1，而 flag=1，1-flag 用的就是数组 0
            flag = 1-flag;
        }

        double total = Math.pow(g_maxValue,number);
        for(int sum = number; sum <= g_maxValue * number;sum++){
            double ratio = (double) probabilities[flag][sum] / total;
            probabilityMap.put(sum,ratio);
        }
        return probabilityMap;
    }



}
